Sen(Qian)’s Memo

参考書一覧

• Foundations of Machine Learning
• 統計的学習理論(MLPシリーズ)

モデル=仮説集合 $ℋ$が存在し、その中で識別器=仮説 $h ∈ ℋ$が存在し、これが二値分類をする。データ $x$に対して、ラベル $y$があり、これに分類器 $h(\mathbf{x})$の出力ができるだけ合致することが望ましく、それが学習である。モデル $ℋ$のなかで、1通りの $y$に対応できることを+1として、その個数を $Π _ℋ(x_1, ⋯, x_n)$とおく。ここで、パラメタは連続値であるので理論上は無限通りのℋのパラメタの取り方が存在するが、同じラベル付けyは1通りとまとめる。

データが $n$個存在するとして、 $2^n$パターンのラベルの付き方が存在する。これについて、 $n$が小さければ$Π _ℋ(x_1, ⋯, x_n) = 2^n$が成り立つ。すなわち、ありうるすべてのラベルの付け方 $y$に対して、パラメタを調節すれば必ずそれを実現する識別器 $h ∈ ℋ$が存在するということである。

$n$が増加していくにあたり、この等式が満たされなくなる=表現力が足りなくなる。この時の最大の $n$をVC次元という。

ラデマッハ複雑度とは、ランダムなノイズに対して学習させるとき、モデルがどれほど追随できるか、という量である。大きいほど表現力が高いモデルである。

ラデマッハ変数という、1/2の確率で+1, 1/2の確率で-1を取る確率変数 $σ$を考える。厳密には $m$個の訓練データ $\mathbf{x}_i$が存在するときのラデマッハ複雑度は以下のように定義する。gは学習器であり、Gは学習器の集合=モデル。

ここで、有限個 $m$個の訓練データで得られた経験的なラデマッハ複雑度は、訓練データを増やした時には、理想的な分布から得られたときと同じ値になる。つまり、不偏推定量。

$ℛ(G)$のなかで、 $G → ϕ(G)$と写像の合成となったときに使える補題。

$ϕ : ℝ → ℝ$であり、リプシッツ連続であるとする。この時、リプシッツ定数 $L$であるとして、以下の不等式が成り立つ。

証明を書く気力はなかった。

$c_i$は次の条件を満たす。 $X _i$を同じく分布に従う別の確率変数 $Y$に変えた時、 $f$の取る値との差の上界にあたる。

ここで、 $f$が $N$変数関数であるが、とりわけ $\mathbf{x} _i$を引数に取って、識別器による経験平均 $\sum _{i = 1} ^ N g(\mathbf{x} _i)$である場合を考える。そして、 $∀\mathbf{x}, g(\mathbf{x}) ∈ [a, b]$と識別器の関数の上界が決まっているのであれば、この式は次のように書くことができる。

そして、一般的には $1 − δ$以上の確率で○○が成り立つ、という形なので、それに式変形する。

このことから、 $∀δ, 1 − δ$以上の確率で、下式が成り立つ。

特に、写す空間が[0, 1]である場合は、以下のように更に略して書ける。

次に重要な定理として、ラデマッハ複雑度を用いた二値分類識別器 $g ∈ 𝒢$の期待値を上から抑えられ、不偏推定量からたかだかどれほどずれるのかを評価できる。これは一様大数の法則と呼ばれている。 $g$は集合 $𝒵 → [a,b]$への写像。なお、 $∀Z ∈ 𝒵$に所属している。また、 $Z_i$はそれぞれ $Z$と独立同分布に従う。 $∀δ, 1 − δ$以上の確率で以下の式が成り立つ。

これを絶対誤差で評価した版は以下である。

$A(z _1, \cdots, z _n) = \sup _{g \in \mathcal{G}} \lbrace \mathbb{E} [ g(Z) ] - \frac{1}{N} \sum _{i = 1} ^ N g(z _i) \rbrace$とする。

ここで、 $Z_n$が $Z ^ \prime$となるとする(同様に𝒵に従う値)。この時、1つだけ変更したとき、上界は以下のようになる。中でのsupは、外の符号が負なので、一番外に出すと最小値のinfになる。infに関しては $f$でなくても、 $g$にするとinfじゃなくなって少し大きくなるので、符号は≤となれる。

これにより、マルチンゲールは $(b − a)/n$となる。これはどの $i$に対しても成り立ち、しかも $A(z _1, \cdots, z ^ \prime) - A(z _1, \cdots, z ^ \prime) \leq \frac{b - a}{n}$も成り立つので、全体で言うと

このことから、先ほどのMcDiarmidの不等式を用いると以下のような集中不等式を得られる。 $∀δ, 1 − δ$以上の確率で、以下が成り立つ。A自体に対して不等式を適用しているということに注目。 $A(z _1, \cdots, z _n) = \sup _{g \in \mathcal{G}} \mathbb{E} [g(Z)] - \frac{1}{n} \sum _{i = 1} ^ n g(z _i)$であり、この中の $g$に対してMcDiarmidの不等式を適用するのではない！なお、普通に $g$で不等式を使うと、 $𝔼[g]$の評価ができなくなるので、このような評価できるかたちで不等式を使った。

次に、 $Z_1, ⋯, Z_n$のみならず、 $Z_1 ^ ′, ⋯, Z_n^′$も $𝒵$に従う確率変数とする。これを使えば、 $𝔼[g]$を $n$個の確率変数に分割できる。つぎに、期待値を外に出すことで、≤の形を作れる。

ここで、対称性により、 $g(Z_i) − g(Z_i^′)$も $g(Z_i^′) − g(Z_i)$も同じ分布を持っている(同じ $𝒵$から来ているし、 $g$も1つである)。だから、符号を自由にflipさせてもいいということになる！符号を自由にflipさせるというのならば、まさにラデマッハ変数じゃないか！あとは三角不等式で評価すればラデマッハ複雑度が出てくる！

このように、上から評価できた！

これを使えば、先ほどのMcDiarmidの不等式から以下の結果が得られる。これこそが、一様大数の法則。

絶対値版に対しては、ここまでの議論で $δ$としていたものを $δ/2$に置き換えると、以下の2つの式が得られる。いずれも $∀δ, 1 − δ/2$以上の確率で成立する。

この2つの式を足し合わせる事で、2で割ると $(1 − δ/2)^2 = 1 − δ + (δ^2/4) ≥ 1 − δ$以上の確率で、